993. Светофоры

В подземелье m тоннелей и n перекрестков, каждый тоннель соединяет какие-то два перекрестка. Мышиный король решил поставить по светофору в каждом тоннеле перед каждым перекрестком. Напишите программу, которая посчитает, сколько светофоров должно быть установлено на каждом из перекрестков. Перекрестки пронумерованы числами от 1 до n.

Вход. В первой строке записано два числа n и m (0 < n ≤ 100, 0 ≤ m ≤ n · (n – 1) / 2). В следующих m строках записаны по два числа i и j (1 ≤ i, j ≤ n), которые означают, что перекрестки i и j соединены тоннелем.

Выход. Вывести n чисел: k-ое число означает количество светофоров на k-ом перекрестке.

Можно считать, что любые два перекрестка соединены не более, чем одним тоннелем. Нет тоннелей от перекрестка i до него самого.

Пример входа	Пример выхода
7 10 5 1 3 2 7 1 5 2 7 4 6 5 6 4 7 5 2 1 5 3	3 3 2 2 5 2 3

РЕШЕНИЕ

графы

Анализ алгоритма

Система перекрестков и тоннелей задает граф. Количество светофоров на k-ом перекрестке равно степени k-ой вершины графа. Тоннели двунаправленные, значит граф неориентированный.

Заведем массив ton, в котором ton[i] будет содержать количество тоннелей, прилегающих к k-му перекрестку. Для каждого неориентированного ребра (a, b) следует увеличить на единицу значения ton[a] и ton[b].

Пример

Граф, приведенный в примере, имеет вид:

Реализация алгоритма

Объявим линейный массив тоннелей ton.

#define MAX 110

int ton[MAX];

Читаем входные данные. Последовательно обрабатываем тоннели, пересчитывая степени вершин графа.

scanf("%d %d",&n,&m);

memset(ton,0,sizeof(ton));

for(i = 0; i < m; i++)

{

scanf("%d %d",&a,&b);

ton[a]++; ton[b]++;

}

Выводим количество светофоров на каждом перекрестке.

for(i = 1; i <= n; i++)

printf("%d ",ton[i]);

printf("\n");